package 代码随想录.链表;

public class _5两两交换链表中的节点 {
    /**
     * 24. 两两交换链表中的节点
     * https://leetcode.cn/problems/swap-nodes-in-pairs/
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     */
    // 递归版本
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }

    //
    public ListNode swapPairs2(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode cur = res;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next!=null && cur.next.next!=null){
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;
            secondnode.next = firstnode;
            firstnode.next = temp;
            cur = firstnode;
        }
        return res.next;
    }

}
